package leetcode.f1t100;

import leetcode.struct.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 中序遍历二叉树
 * https://leetcode.com/problems/binary-tree-inorder-traversal/
 *
 * @author lichx
 * @createTime 2024/2/19 15:00
 */
public class Q94_BinaryTreeInorderTraversal {

    public static void main(String[] args) {
        Q94_BinaryTreeInorderTraversal bean = new Q94_BinaryTreeInorderTraversal();
        List<Integer> list = bean.inorderTraversal(new TreeNode(1, null, new TreeNode(2, new TreeNode(3), null)));
        System.out.println(list);
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
//        inorderTraversalRecursion(root, ans);
//        inorderTraversalNotRecursion(root, ans);
        inorderTraversalOneStack(root, ans);
        return ans;
    }

    private void inorderTraversalRecursion(TreeNode root, List<Integer> ans) {
        if(root == null) {
            return;
        }
        inorderTraversalRecursion(root.left, ans);
        ans.add(root.val);
        inorderTraversalRecursion(root.right, ans);
    }

    private void inorderTraversalNotRecursion(TreeNode root, List<Integer> ans) {
        Stack<TreeNode> stack1 = new Stack<>(), stack2 = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack1.isEmpty() || !stack2.isEmpty()) {
            if(cur!= null) {
                stack1.push(cur);
                cur = cur.left;
                continue;
            }
            if(!stack2.isEmpty()) {
                stack2.pop();
                continue;
            }
            if(!stack1.isEmpty()) {
                cur = stack1.pop();
                stack2.push(cur);
                ans.add(cur.val);
                cur = cur.right;
            }
        }
    }

    private void inorderTraversalOneStack(TreeNode root, List<Integer> ans) {
        Stack<TreeNode> stack = new Stack<>();
        while(root != null || !stack.isEmpty()) {
            while(root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            ans.add(root.val);
            root = root.right;
        }
    }
}